'''
https://leetcode.cn/problems/number-of-distinct-islands/description
'''
from typing import List


class Solution:
    def numIslands2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        seen = [[False] * n for _ in range(m)]

        def dfs(i, j, path):
            for tx, ty, s in ((0, 1, 'R'), (0, -1, 'L'), (1, 0, 'D'), (-1, 0, 'U')):
                tx, ty = i + tx, j + ty
                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1 and not seen[tx][ty]:
                    seen[tx][ty] = True
                    path.append(s)
                    dfs(tx, ty, path)
            path.append('O')

        dic = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not seen[i][j]:
                    seen[i][j] = True
                    path = ['O']
                    dfs(i, j, path)
                    if path:
                        dic.add('->'.join(path))
        print(dic)
        return len(dic)


grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
print(Solution().numIslands2(grid))